#include "param.h"
#include "types.h"
#include "defs.h"
#include "x86.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "elf.h"

extern char data[];  // defined by kernel.ld
pde_t *kpgdir;  // for use in scheduler()

// Set up CPU's kernel segment descriptors.
// Run once on entry on each CPU.
void
seginit(void)
{
  struct cpu *c;

  // Map "logical" addresses to virtual addresses using identity map.
  // Cannot share a CODE descriptor for both kernel and user
  // because it would have to have DPL_USR, but the CPU forbids
  // an interrupt from CPL=0 to DPL=3.
  c = &cpus[cpuid()];
  c->gdt[SEG_KCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, 0);
  c->gdt[SEG_KDATA] = SEG(STA_W, 0, 0xffffffff, 0);
  c->gdt[SEG_UCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, DPL_USER);
  c->gdt[SEG_UDATA] = SEG(STA_W, 0, 0xffffffff, DPL_USER);
  lgdt(c->gdt, sizeof(c->gdt));
}

// Return the address of the PTE in page table pgdir
// that corresponds to virtual address va.  If alloc!=0,create any required page table pages.  
// 当alloc=1时，如果页目录项是没映射的，就会申请一页物理内存进行映射，当alloc=0时，如果页目录项没映射，那就直接返回0，不需要映射，在deallocuvm和loaduvm函数里调用时alloc=0
// alloc为0通常是为了检查页目录项是否有被映射，有映射再返回页表项，页目录项都没映射，那页表项肯定没映射，页表项要想映射就得先映射页目录项
// 【重要！！！】本系统是二级页表系统，一级页表存页目录项，指向n个二级页表的 物理地址 ，二级页表存页表项，映射待写的物理内存
// 获取虚拟地址所对应的页表项，页表项可用虚拟地址直接在页表数组里进行索引
// walkpgdir这个名字表明只是遍历页目录表，
static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  //pte指向页表项，pde指向页目录项，本系统是二级页表，使用pde指针指向该页目录项
  pde_t *pde;  //页目录项地址，指向二级页表所在位置
  pte_t *pgtab;//页表项地址

  //PDX是获取虚拟地址va对应的 页目录项
  pde = &pgdir[PDX(va)]; //通过va的上n位索引到页目录项并获取其指向页表的地址，该地址是否有效得看PTE_P标志位判断
  if(*pde & PTE_P){  // PTE_P是页表项/页目录项存在位，表明该页表项/页目录项是否已映射到某一物理内存
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde));  //此时1级页目录表里的这个页目录项已经被映射到了某个物理地址，所以便根据 页目录项 获取其所指向的 页表 所在的有效物理地址对应的虚拟地址
                                          //因为此时pde是已映射的页表项的地址，其指向的单位所保存的值是虚拟地址对应的物理地址，因此要用P2V转成虚拟地址
  } else {  // 表示页目录项未映射物理内存，即指向的页表还没被映射和加载到物理内存中
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0)  // 申请新的一页空间，作为页表数组，alloc标志位指明是否允许申请物理内存页用于存放页表，可能是为了内存的使用来考虑的
      return 0;
    // Make sure all those PTE_P bits are zero.
    memset(pgtab, 0, PGSIZE); //先把该页表全清0，毕竟之前页目录项没映射到此表，所以此表里面的页表项肯定也全都没映射
    // The permissions here are overly generous, but they can
    // be further restricted by the permissions in the page table entries, if necessary.
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;   // 给新页表项设置一些标志位，并且复制给指向此页表对应的页目录项，两者标志位是一样的
  }
  return &pgtab[PTX(va)];  //PTX是获取虚拟地址va对应的页表项，上面的PDX是获取虚拟地址va对应的页目录项，到return这里必定会返回页表项
}

// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. va地址不用对齐，因为代码会自动找到va下对齐的页首地址
// 进行一大段虚拟内存和物理内存的页映射
// 完成映射返回0，失败返回-1
static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;

  a = (char*)PGROUNDDOWN((uint)va);  // 获取需要映射的一大段虚拟内存 的 页表对齐下界地址，用于判断是否完成映射
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1); // 获取需要映射的一大段虚拟内存 的 页表对齐上界地址
  for(;;){ // 连续映射，因为这一大段虚拟内存可能需要好几个页才能映射完整
    if((pte = walkpgdir(pgdir, a, 1)) == 0) //获取虚拟地址所对应的页表项，页表项可用虚拟地址直接在页表数组里进行索引
      return -1; // 失败

    if(*pte & PTE_P) // 页表项已经存在
      panic("remap"); // 则报错“重复映射”

    *pte = pa | perm | PTE_P; // 设置对应的物理地址和权限位，因为walkpgdir会一口气索引二级页表，最终找到的不是页目录项，而是页表项

    if(a == last) // 因为虚拟地址从va开始的size大小的空间可能需要好几个页才能映射完全，所以此处是看是否已经一整段虚拟内存全都映射完成
      break;
    a += PGSIZE;
    pa += PGSIZE; // 如果还没映射完成，那就++PGSIZE继续映射
  }
  return 0; //完成映射后返回0
}

// There is one page table per process, plus one that's used when    //多出了一个页表kpgdir
// a CPU is not running any process (kpgdir). The kernel uses the
// current process's page table during system calls and interrupts;
// page protection bits prevent user code from using the kernel's
// mappings.
//
// setupkvm() and exec() set up every page table like this:
//
//   0..KERNBASE: user memory (text+data+stack+heap), mapped to
//                phys memory allocated by the kernel
//   KERNBASE..KERNBASE+EXTMEM: mapped to 0..EXTMEM (for I/O space)
//   KERNBASE+EXTMEM..data: mapped to EXTMEM..V2P(data)
//                for the kernel's instructions and r/o data
//   data..KERNBASE+PHYSTOP: mapped to V2P(data)..PHYSTOP,
//                                  rw data + free physical memory
//   0xfe000000..0: mapped direct (devices such as ioapic)
//
// The kernel allocates physical memory for its heap and for user memory
// between V2P(end) and the end of physical memory (PHYSTOP)
// (directly addressable from end..P2V(PHYSTOP)).

// This table defines the kernel's mappings, which are present in
// every process's page table.
// 内核映射表，会出现在每一个进程页表中
static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space   好像是BIOS
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory    这项和上面一共3部分，将连续的虚拟内存KERNBASE:KERNBASE+PHYSTOP映射到物理内存0:PHYSTOP
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices   这个采用直接映射
};

// Set up kernel part of a page table.
// setupkvm函数 返回页目录表地址，页目录表在下面这个函数作了初始化，即映射了kmap中的内核页到物理内存中，该内核页表记录了内核表被映射到物理内存后的映射信息
pde_t*
setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  if((pgdir = (pde_t*)kalloc()) == 0) //申请一个页面，作为页目录，存放页目录项（所以地址类型为pde_t*），把该页的首地址赋给了pgdir
    return 0;
  memset(pgdir, 0, PGSIZE);  //将页面清0

  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");  //内存太大

  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)   //不断映射内核部分的内存，会将页目录项和页表项一起完成映射
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
                (uint)k->phys_start, k->perm) < 0) {  
        //映射失败
      freevm(pgdir);
      return 0;
    }
  return pgdir;  //内核部分的内存映射完成后返回页目录地址
}

// Allocate one page table for the machine for the kernel address
// space for scheduler processes.
void
kvmalloc(void)
{
  kpgdir = setupkvm();  
  switchkvm();
}

// Switch h/w page table register to the kernel-only page table,
// for when no process is running.
// 切换至内核虚拟内存
void
switchkvm(void)
{
  lcr3(V2P(kpgdir));   // switch to the kernel page table  CR3寄存器用于存储当前页目录的物理地址。在entry.S中也有设置过
}

// Switch TSS and h/w page table to correspond to process p.
// 用于切换到用户进程的虚拟内存空间和任务状态段（TSS）
void
switchuvm(struct proc *p)
{
  if(p == 0)
    panic("switchuvm: no process");
  if(p->kstack == 0)
    panic("switchuvm: no kstack");
  if(p->pgdir == 0)
    panic("switchuvm: no pgdir");

  pushcli(); // 关闭中断

  //更新任务状态段中的内核栈指针和数据段选择符，确保在内核模式下切换到正确的内核栈和数据段
  mycpu()->gdt[SEG_TSS] = SEG16(STS_T32A, &mycpu()->ts,
                                sizeof(mycpu()->ts)-1, 0);
  mycpu()->gdt[SEG_TSS].s = 0;
  mycpu()->ts.ss0 = SEG_KDATA << 3;
  mycpu()->ts.esp0 = (uint)p->kstack + KSTACKSIZE;
  // setting IOPL=0 in eflags *and* iomb beyond the tss segment limit
  // forbids I/O instructions (e.g., inb and outb) from user space
  mycpu()->ts.iomb = (ushort) 0xFFFF;
  //-------------------------------------------------------------------------

  ltr(SEG_TSS << 3); // 加载任务状态段寄存器（TR），使其指向新的任务状态段。
  lcr3(V2P(p->pgdir));  // switch to process's address space   CR3寄存器用于存储当前页目录的物理地址。在entry.S中也有设置过
  popcli(); // 开中断
}

// Load the initcode into address 0 of pgdir.
// sz must be less than a page.
// 分配一页物理内存，将虚拟地址0映射到那一段内存，并把*init指向的一段代码拷贝到那一页中，第一个进程的初始化主要把initcode.S的程序拷贝进去
void
inituvm(pde_t *pgdir, char *init, uint sz)
{
  char *mem;

  if(sz >= PGSIZE) //这个initcode.S的大小不能大于一页
    panic("inituvm: more than a page");
  mem = kalloc(); //申请一页物理内存，返回首地址。   其实mem仍然是虚拟地址，但是可以通过虚拟地址和宏函数V2P(mem)直接找到物理地址，此时mem并没有被映射
  memset(mem, 0, PGSIZE); //初始化这个页为0
  mappages(pgdir, 0, PGSIZE, V2P(mem), PTE_W|PTE_U);  //将虚拟地址0映射到mem页面的物理内存
                                                      //因为使用的是V2P(mem)，所以kalloc分配的mem是虚拟地址 并没有被映射到物理内存中，只有mappages函数才是真正执行了内存映射

  //PTE_W|PTE_U：页表项的权限标志，PTE_W 表示可写，PTE_U 表示用户模式可访问。
  memmove(mem, init, sz); //将init为首地址的大小为sz的空间拷贝到mem虚拟内存页里
}

// Load a program segment into pgdir.  addr must be page-aligned
// and the pages from addr to addr+sz must already be mapped.
// 将一个程序段（a program segment）装入虚拟内存addr～addr+sz，程序段必须页对齐，且装入的目标地址必须已映射
int
loaduvm(pde_t *pgdir, char *addr, struct inode *ip, uint offset, uint sz)
{
  uint i, pa, n;
  pte_t *pte;

  if((uint) addr % PGSIZE != 0)
    panic("loaduvm: addr must be page aligned"); //没有页对齐
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walkpgdir(pgdir, addr+i, 0)) == 0)
      panic("loaduvm: address should exist");  //待装入的目标页没有映射
    pa = PTE_ADDR(*pte);  // 得到页表项所指向的页面的物理地址
    if(sz - i < PGSIZE)   // 计算当前页需要读取的字节数。如果剩余的数据小于一个页的大小，则只读取剩余的数据.
      n = sz - i;    //i是不断自增PGSIZE的，sz是不一定PGSIZE对齐的
    else
      n = PGSIZE;

    if(readi(ip, P2V(pa), offset+i, n) != n) // 调用 readi 函数从文件的 offset+i 位置读取 n 字节的数据到物理地址 pa 对应的虚拟地址 P2V(pa)
      return -1;
  }
  return 0;
}

// 该函数在proc.c的growproc函数里调用了
// Allocate page tables and physical memory to grow process from oldsz to
// newsz（将进程从oldsz扩展到newsz）, which need not be page aligned（不需要页面对齐）.  
// Returns new size or 0 on error.
// 此函数的作用是 扩增内存页并完成映射（从原内存空间上界页的虚拟地址开始，不断映射到新扩增内存页的物理地址）
int
allocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
  char *mem;
  uint a;

  if(newsz >= KERNBASE)
    return 0;  //太大了
  if(newsz < oldsz)
    return oldsz; //新的size需要大于旧的size，“减少内存”不是这个函数该做的，所以返回

  a = PGROUNDUP(oldsz);  // 将oldsz进行页面对齐，得到上界地址
  for(; a < newsz; a += PGSIZE){  //循环进行扩容
    mem = kalloc(); //分配内存页
    if(mem == 0){  //kalloc返回0代表物理内存分完了
      cprintf("allocuvm out of memory\n");
      deallocuvm(pgdir, newsz, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE); //把新内存清0
    if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){  // mappages将新分配的内存进行映射，因为是扩容，所以从oldsz的上界虚拟地址a开始映射到新内存页mem的物理地址
      // 失败时
      cprintf("allocuvm out of memory (2)\n");
      deallocuvm(pgdir, newsz, oldsz);
      kfree(mem);
      return 0;
    }
  }
  return newsz;
}

// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
int
deallocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
  pte_t *pte;
  uint a, pa;

  if(newsz >= oldsz) //新size需要小于旧的size，因为是减少内存，否则返回旧的size
    return oldsz;

  a = PGROUNDUP(newsz);   // 将newsz进行页面对齐，得到上界地址
  for(; a  < oldsz; a += PGSIZE){ // 从newsz开始往上，将newsz和oldsz之间的内存页全释放掉
    pte = walkpgdir(pgdir, (char*)a, 0); //首先还是需要得到页表项，alloc标志位设为0，表示如果没映射那就不需要映射了，因为此处为了删除，怎么方便怎么来
    if(!pte)  // alloc标志位为0时walkpgdir函数返回0，说明页目录项没映射，则说明以这个a地址对应的页目录项及其指向的一整个页表都没有被映射
      a = PGADDR(PDX(a) + 1, 0, 0) - PGSIZE; // PGADDR 使用页目录索引、页表索引、页内偏移 三者还原出此虚拟地址
                              // 此处【PDX(a)+1】直接在页目录索引加了1,相当于是a+=1024*PGSIZE，跨越了2^22Byte=4MB空间，也就是在第22位加了1，PDX正好是原虚拟地址右移22位后的数
                              // 后面的 减去PGSIZE是为了抵消for循环自增，原本每次循环跨越4KB空间，这次直接跨越1024*4KB = 4MB = 2^22Byte
    else if((*pte & PTE_P) != 0){ // walkpgdir没返回0表示页目录项有映射，其所指向的页表有映射到某个物理内存页面里，此时还需要页表项也被映射了，此处逻辑只为了防止把内核页面给释放了
      pa = PTE_ADDR(*pte); // 页表项有被映射，于是获取该页表项映射的物理内存页地址，即页表项的高20位，它的低12位作为页内偏移 全置0
      if(pa == 0) //如果物理地址为0
        panic("kfree"); //报错：表示此时释放的是内核，因为内核在一开始的userinit的setupkvm函数里被映射到了物理地址0的页面里
      char *v = P2V(pa);  // 如果物理地址没问题，可以释放，那就获取其对应的虚拟地址
      kfree(v); // 以虚拟地址为参数释放内存页，就是将此虚拟内存地址作为空闲链表项插入空闲链表
      *pte = 0; // 将该被释放的内存页所对应的页表项清0，把这个页表项变成未映射状态
    }
  }
  return newsz;
}

// Free a page table and all the physical memory pages  用户层调用的释放页表及其所有页表项映射的物理内存页面
// in the user part.
void
freevm(pde_t *pgdir)
{
  uint i;

  if(pgdir == 0) // 页目录不存在
    panic("freevm: no pgdir");
  deallocuvm(pgdir, KERNBASE, 0); // 调用删减内存的函数，将0～KERNBASE的所有虚拟地址空间的页对应的页表项都清0取消映射，并将页面的虚拟首地址加入空闲页链表
  for(i = 0; i < NPDENTRIES; i++){  //NPDENTRIES是一个页目录表里的页目录项个数，为1024，自己能算
    if(pgdir[i] & PTE_P){  // 上面是复位页表项，现在这里是复位页目录项，页目录项对应的存着页表的页面也要释放
      char * v = P2V(PTE_ADDR(pgdir[i]));
      kfree(v);
    }
  }
  kfree((char*)pgdir);  // 最后把存放页目录的页面也释放掉
}

// Clear PTE_U on a page. Used to create an inaccessible
// page beneath the user stack.  //此函数取消 以uva为首地址的页 的用户访问权限
void
clearpteu(pde_t *pgdir, char *uva)
{
  pte_t *pte;

  pte = walkpgdir(pgdir, uva, 0); // 找到以uva为首地址的页对应的页表项并放回给pte
  if(pte == 0) // 如果得到的是0，就证明此页目录项及里面的页表项根本没映射
    panic("clearpteu");
  *pte &= ~PTE_U;// 如果确实有映射，那就去除PTE_U位
}

// Given a parent process's page table, create a copy
// of it for a child.
pde_t*
copyuvm(pde_t *pgdir, uint sz)
{
  pde_t *d;
  pte_t *pte;
  uint pa, i, flags;
  char *mem;

  if((d = setupkvm()) == 0)
    return 0;
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walkpgdir(pgdir, (void *) i, 0)) == 0)
      panic("copyuvm: pte should exist");
    if(!(*pte & PTE_P))
      panic("copyuvm: page not present");
    pa = PTE_ADDR(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto bad;
    memmove(mem, (char*)P2V(pa), PGSIZE);
    if(mappages(d, (void*)i, PGSIZE, V2P(mem), flags) < 0) {
      kfree(mem);
      goto bad;
    }
  }
  return d;

bad:
  freevm(d);
  return 0;
}

//PAGEBREAK!
// Map user virtual address to kernel address.
// 其实不太明白跟kernel address有什么关系，从代码看来可能只是确认一下该虚拟地址所在的页对应的页表项信息，确认是否有效、确认用户是否可写
// 确认通过再返回页表项记录的物理地址对应的虚拟地址
char*
uva2ka(pde_t *pgdir, char *uva)
{
  pte_t *pte;

  pte = walkpgdir(pgdir, uva, 0); //获得uva地址所在页面对应的页表项
  if((*pte & PTE_P) == 0) //查看有效位，确认该页表项是否已映射
    return 0;
  if((*pte & PTE_U) == 0) //查看权限，确认用户是否可写
    return 0;
  return (char*)P2V(PTE_ADDR(*pte)); //将PTE页表项所记录的物理地址转成虚拟地址后，类型转换为char*地址然后返回
}

// Copy len bytes from p to user address va in page table pgdir.
// Most useful when pgdir is not the current page table.
// uva2ka ensures this only works for PTE_U pages.
// 从地址p处开始拷贝len字节的数据到虚拟地址va
int
copyout(pde_t *pgdir, uint va, void *p, uint len)
{
  char *buf, *pa0;
  uint n, va0;

  buf = (char*)p;
  while(len > 0){
    va0 = (uint)PGROUNDDOWN(va); //获取va地址的页下界
    pa0 = uva2ka(pgdir, (char*)va0); //确认该虚拟地址所在页对应的页表项的用户权限和有效位
    if(pa0 == 0)
      return -1; //出错，因为上一步uva2ka函数的权限检测和有效检测不符合
    n = PGSIZE - (va - va0);// 此处是获取待写地址与页上界地址之间的空间大小（注意内存里是由低地址往高地址写的）
    if(n > len)
      n = len; //如果剩余空间大于len，则可用于存储，并把n记录为len 用于表示拷贝长度。
    //但如果剩余空间不足，即n<len，则只拷贝剩余空间大小n个字节，剩下的len-n留到下一次循环继续写，因为下一个页的写入又需要通过uva2ka函数检查权限
    memmove(pa0 + (va - va0), buf, n); //从buf里拷贝n字节数据到
    len -= n; // 记录剩余待写长度，如果之前n > len，那么len-=n后会等于0
    buf += n; // 记录已写的偏移，如果之前n > len，那么此时buf应该就到达最后一个字节了
    va = va0 + PGSIZE; // va直接等于下一页页首地址，假如之前已经写完了，那这句就没什么用了
  }
  return 0;
}

//PAGEBREAK!
// Blank page.
//PAGEBREAK!
// Blank page.
//PAGEBREAK!
// Blank page.

